from dataclasses import dataclass


@dataclass
class Plan:
    money: float
    plan: list


class Solution:
    def __init__(self, gap, targetMoney):

        self.res = []
        self.gap = gap
        self.targetMoney = targetMoney

    def getPlan(
        self, targetMoney, moneys: list = [], curren_money: list = [], index: int = 0
    ) -> None:

        if sum(curren_money) > targetMoney:
            return

        if (
            sum(curren_money) == targetMoney
            or targetMoney - sum(curren_money) <= self.gap
        ):
            self.res.append(Plan(money=sum(curren_money), plan=curren_money.copy()))

        for i in range(index, len(moneys)):
            money = moneys[i]
            if not curren_money or targetMoney >= sum(curren_money):
                curren_money.append(money)
                self.getPlan(targetMoney, moneys, curren_money, i + 1)
                curren_money.pop()
        return

    def exe(self, money_list: list):
        self.getPlan(targetMoney=self.targetMoney, moneys=money_list)
        return self.res


def main():
    money_list = [50, 10, 40]
    targetMoney = 50
    gap = 10
    solution = Solution(gap=gap, targetMoney=targetMoney)

    res = solution.exe(money_list=money_list)

    print("输出最优方案：")
    sorted_res = sorted(res, key=lambda x: x.money, reverse=True)
    print(sorted_res)
    # for i, key in enumerate(sorted_dic):
    #     if i < planNum:
    #         print(f"总金额: {key}, 方案: {sorted_dic[key]}")
    #     else:
    #         break


if __name__ == "__main__":
    main()
